package com.datastructure2.greedyalgorithm;

import org.junit.Test;

import javax.xml.bind.PrintConversionEvent;
import java.util.*;

/**
 * @author: 临晖
 * @date: 2024/03/02
 * @description:
 */
public class Solution {

    /**
     * 455. 分发饼干
     * 简单
     * 相关标签
     * 相关企业
     * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
     * 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，
     * 都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
     *
     * @param g
     * @param s
     * @return
     */
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);     //小孩胃口
        Arrays.sort(s);     //饼干
        int count = 0;
        for (int i = s.length - 1, j = g.length - 1; i >= 0 && j > 0; i--, j--) {
            if (s[i] >= g[j]) {
                count++;
            } else {
                i++;
            }
        }
        return count;
    }


    /**
     * 376. 摆动序列
     * 中等
     * 相关标签
     * 相关企业
     * 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
     *
     * @param nums
     * @return
     */
    public int wiggleMaxLength(int[] nums) {
        int count = 1;

        if (nums.length <= 1) {
            return count;
        }

        int preDiff = 0;
        int curDfff = 0;

        for (int i = 1; i < nums.length; i++) {
            curDfff = nums[i] - nums[i - 1];

            //条件判断
            if ((preDiff <= 0 && curDfff > 0) || (preDiff >= 0 && curDfff < 0)) {
                count++;
                preDiff = curDfff;
            }
        }

        return count;
    }


    /**
     * 53. 最大子数组和
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * 子数组
     * 是数组中的一个连续部分。
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int maxRes = Integer.MIN_VALUE;
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];

            if (sum > maxRes) {
                maxRes = sum;
            }

            if (sum <= 0) {
                sum = 0;
            }
        }

        return maxRes;

    }


    /**
     * 122. 买卖股票的最佳时机 II
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {

        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - prices[i - 1] > 0) {
                sum += (prices[i] - prices[i - 1]);
            }
        }

        return sum;
    }


    /**
     * 55. 跳跃游戏
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     *
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {

        int max = 0;
        for (int i = 0; i <= max; i++) {
            if (i + nums[i] > max) {
                max = i + nums[i];
            }

            if (max >= nums.length - 1) {
                return true;
            }


        }
        return false;
    }


    /**
     * 45. 跳跃游戏 II
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }

        int ans = 0;
        int currJump = 0;
        int nextJump = 0;

        for (int i = 0; i < nums.length; i++) {
            nextJump = Math.max(nextJump, i + nums[i]);


            if (i == currJump) {
                ans++;
                currJump = nextJump;
                if (nextJump >= nums.length - 1) {
                    break;
                }
            }
        }

        return ans;


    }


    /**
     * 1005. K 次取反后最大化的数组和
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
     * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
     * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
     * 以这种方式修改数组后，返回数组 可能的最大和 。
     *
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int k) {
        //思路：
        //nums升序
        //记录nums中负数的个数n
        //  k大于n： (k - n) % 2 == 0;不变，否则，取反
        //  k小于n:

        //Arrays.sort(nums);      //排序
        int sum = 0;


        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] <= 0) {
                nums[i] = -nums[i];
                k--;
            }
            sum += nums[i];
        }

        //俩种可能：k消耗完，还有负数
        //          k未消耗完，负数还有

        if (k == 0 || (k % 2 == 0)) {
            return sum;
        } else {
            Arrays.sort(nums);
            sum -= (2 * nums[0]);
        }
        return sum;
    }


    /**
     * @param gas  加油量
     * @param cost 消耗油量
     * @return
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {


        int minGap = 0;
        int sum = 0;
        for (int i = 0; i < cost.length; i++) {
            sum += (gas[i] - cost[i]);
            minGap = Math.min(sum, minGap);
        }

        if (sum < 0) {
            return -1;
        }

        if (minGap >= 0) {
            return 0;
        }

        for (int i = gas.length - 1; i > 0; i--) {
            minGap += (gas[i] - cost[i]);
            if (minGap >= 0) {
                return i;
            }
        }

        return -1;

    }


    /**
     * 135. 分发糖果
     * 困难
     * 相关标签
     * 相关企业
     * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
     * 你需要按照以下要求，给这些孩子分发糖果：
     * 每个孩子至少分配到 1 个糖果。
     * 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
     *
     * @param ratings
     * @return
     */
    public int candy(int[] ratings) {
        int[] candy = new int[ratings.length];

        //从前面遍历，考虑右边比左边的孩子大
        for (int i = 0; i < ratings.length; i++) {
            if (i > 0 && ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            } else {
                candy[i] = 1;
            }
        }

        //从后面遍历，考虑左边比右边的孩子大
        for (int i = ratings.length - 1; i >= 0; i--) {
            if (i < ratings.length - 1 && ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i + 1] + 1, candy[i]);
            }
        }


        int sum = 0;
        for (int x : candy) {
            sum += x;
        }
        return sum;
    }


    /**
     * 860. 柠檬水找零
     * 简单
     * 相关标签
     * 相关企业
     * 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
     * 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
     * 注意，一开始你手头没有任何零钱。
     * 给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
     *
     * @param bills
     * @return
     */
    public boolean lemonadeChange(int[] bills) {

        int five = 0;
        int ten = 0;

        for (int bill : bills) {
            if (bill == 5) {        //如果给了五元直接收下
                five++;
            }

            if (bill == 10) {       //如果给了十元
                if (five <= 0) {     //没有五元零钱，直接false
                    return false;
                }
                five--;
                ten++;
            }

            if (bill == 20) {       //如果给了20元
                if (five <= 0) {            //第一：如果没有五元，直接false
                    return false;
                }

                //第二：有10元
                if (ten > 0) {
                    ten--;
                    five--;
                } else {        //没有10元
                    if (five < 3) {
                        return false;
                    }
                    five -= 3;
                }

                //收入20
            }
        }

        return true;
    }


    /**
     * 406. 根据身高重建队列
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
     * <p>
     * 不能俩边同时考虑，先考虑一边，在考虑另一半
     *
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                }
                return o2[0] - o1[0];
            }
        });

        LinkedList<int[]> que = new LinkedList<>();
        for (int[] peo : people) {
            que.add(peo[1], peo);

        }
        return que.toArray(new int[people.length][]);
    }


    /**
     * 452. 用最少数量的箭引爆气球
     * 中等
     * 相关标签
     * 相关企业
     * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
     *
     * @param points
     * @return
     */
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o2[0] == o1[0]) {
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });
        int count = 0;
        int left = points[0][0];
        int right = points[0][1];
        for (int i = 1; i < points.length; i++) {
            //int left1 = points[i - 1][0];
            //int right1 = points[i - 1][1];

            int left1 = points[i][0];
            int right1 = points[i][1];

            if (left1 <= right) {
                left = left1;
            } else {
                left = left1;
                right = right1;
                count++;
                continue;
            }

            if (right1 <= right) {
                right = right1;
            }
        }

        return count++;
    }


    /**
     * 435. 无重叠区间
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
     *
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        int count = 0;
        if (intervals.length == 1) {
            return count;
        }

        //排序，升序
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });


        int end = intervals[0][1];
        int currIndex = 1;
        for (; currIndex < intervals.length; currIndex++) {
            int left = intervals[currIndex][0];

            if (left < end) {
                count++;
                end = Math.min(end, intervals[currIndex][1]);       //如果不符合条件，那么end 取小值
            } else {
                end = intervals[currIndex][1];      //如果符合条件，end跳到下一个
            }


        }

        return count;
    }


    /**
     * 763. 划分字母区间
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
     * 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
     * 返回一个表示每个字符串片段的长度的列表。
     *
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {
        int end = 0;
        int pre = 0;
        ArrayList<Integer> res = new ArrayList<>();

        for (int i = 0; i < s.length(); i++) {

            if (i > end) {
                res.add(end - pre + 1);
                pre = end + 1;

            }

            end = Math.max(end, s.lastIndexOf(s.charAt(i)));
        }


        res.add(end - pre + 1);


        return res;
    }

    /**
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }

        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });

        int startIndex = 0;
        int end = intervals[startIndex][1];

        ArrayList<int[]> res = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {

            if (intervals[i][0] <= end) {
                end = Math.max(end, intervals[i][1]);
            } else {
                res.add(new int[]{intervals[startIndex][0], end});
                startIndex = i;
                end = intervals[i][1];
            }
        }

        res.add(new int[]{intervals[startIndex][0], end});

        return res.toArray(new int[][]{});
    }


    /**
     * 738. 单调递增的数字
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
     * 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增
     *
     * @param n
     * @return
     */
    public int monotoneIncreasingDigits(int n) {
        char[] array = (n + "").toCharArray();
        if (array.length == 1) {
            return n;
        }


        int flag = array.length - 1;
        for (int i = array.length - 2; i >= 0; i--) {
            if (array[i] > array[i + 1]) {
                array[i] -= 1;
                flag = i;
            }
        }

        for (int i = flag; i < array.length; i++) {
            array[i] = '9';
        }

        return Integer.parseInt(new String(array));
    }


    /**
     * 968. 监控二叉树
     * 困难
     * 相关标签
     * 相关企业
     * 给定一个二叉树，我们在树的节点上安装摄像头。
     * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
     * 计算监控树的所有节点所需的最小摄像头数量。
     *
     * @param root
     * @return
     */
    int res = 0;

    public int minCameraCover(TreeNode root) {
        // 对根节点的状态做检验,防止根节点是无覆盖状态 .
        if (minCame(root) == 0) {
            res++;
        }
        return res;
    }

    /**
     * 节点的状态值：
     * 0 表示无覆盖
     * 1 表示 有摄像头
     * 2 表示有覆盖
     * 后序遍历，根据左右节点的情况,来判读 自己的状态
     */
    public int minCame(TreeNode root) {
        if (root == null) {
            // 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头
            return 2;
        }
        int left = minCame(root.left);
        int right = minCame(root.right);

        // 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
        if (left == 2 && right == 2) {
            //(2,2)
            return 0;
        } else if (left == 0 || right == 0) {
            // 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头
            // (0,0) (0,1) (0,2) (1,0) (2,0)
            // 状态值为 1 摄像头数 ++;
            res++;
            return 1;
        } else {
            // 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，
            // 那么本节点就是处于被覆盖状态
            return 2;
        }

    }


    @Test
    public void myTest() {
        System.out.println(monotoneIncreasingDigits(10));
    }
}


/**
 * 裤子：
 */
